package com.hy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:2316. 统计无向图中无法互相到达点对数
 * <p>
 * 给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，
 * 其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
 * 请你返回 无法互相到达 的不同 点对数目 。
 * <p>
 * User:Mr.Du
 * Date:2024/4/18
 * Time:9:48
 */
public class CountPairs {

    /**
     * 统计无向图中无法互相到达点对数
     * @param n 节点的总数。
     * @param edges 边的集合，每个边由两个节点索引组成。
     * @return 形成的pair数量。
     */
    public long countPairs(int n, int[][] edges) {
        long res = 0, total = 0; // res用于累计结果，total用于记录已访问节点的总数
        List<Integer>[] list = new List[n]; // list为邻接表，存储每个节点的邻居节点
        boolean[] visited = new boolean[n]; // visited标记数组，记录节点是否被访问过
        Arrays.setAll(list, i -> new ArrayList<>()); // 初始化邻接表，每个节点的邻居列表为空

        // 建立边的邻接表表示
        for(int[] edge : edges){
            int x = edge[0], y = edge[1];
            list[x].add(y); // 添加邻居节点
            list[y].add(x); // 由于是无向图，需要双向添加
        }

        // 遍历每个节点，计算以该节点为起点能够形成的pair数量
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                // 如果节点未被访问，则进行深度优先搜索
                int count = dfs(list, visited, i);
                res += count * total;
                total += count;
            }
        }
        return res; // 返回
    }

    /**
     * 使用深度优先搜索（DFS）算法计算给定图中以指定节点为根的树的节点数量。
     * @param list 一个邻接表，表示图的结构，list[i] 包含节点 i 直接相连的所有节点。
     * @param visited 一个布尔数组，用于标记节点是否已被访问，初始状态下所有节点都未被访问。
     * @param i 当前正在访问的节点的索引。
     * @return 返回以节点 i 为根的树的节点数量。
     */
    private int dfs(List<Integer>[] list, boolean[] visited, int i) {
        visited[i] = true; // 标记当前节点为已访问
        int size = 1; // 初始化当前树的节点数量为1，即根节点自身

        // 遍历当前节点的所有邻接节点
        for(int x : list[i]){
            if(!visited[x]){ // 如果邻接节点未被访问过
                // 递归计算该邻接节点为根的子树节点数量，并累加到当前树的节点数量上
                size += dfs(list, visited, x);
            }
        }
        
        return size; // 返回当前树的节点数量
    }


}
